package com.noahsloan.groovy.algorithms

import com.noahsloan.groovy.util.DelegateObject

/**
 * @author noah
 *
 */
public class TestGraphAlgorithms extends GroovyTestCase {
	
	def graph
	def algo
	def n = { new Node(data:it) }
	
	void setUp() throws Exception{
		// XXX inlining toString causes the owner == createEdge 
		// createEdge.delegate == node
		// node.prototype == null (not MissingPropertyException b/c Expando)
		// owner.delegate is processed before delegate
		// QED
		def edgeProps = [toString:{
			"${prototype} [label=\"${cost?:'1'}\"]"
		}]
		def builder = new GraphBuilder(createGraphNode:{ data, props ->
			def node = GraphAlgorithms.createNode(data,props)
			node.createEdge = { a, b, attrs = [:] ->
				new DelegateObject(GraphAlgorithms.createEdge(a,b,attrs),edgeProps)
			}
			node
		})
		builder.node("a") {
			node("b") {
				edge("a")
				edge("c"){ cost(-1) }
			}
			node("c") {
				node("d")
				node("e") {
					node("f")
				}
			}
			node("g") {
				edge("h")
				edge("n")
			}
		}
		builder.node("i") {
			node("j") {
				edge("i"){ cost(5) }
			}
			node("k") {
				edge("n"){ cost(-2) }
			}
			node("l") {
				node("m")
				node("n") {
					edge("d")
					edge("g"){ cost(3) }
					edge("a"){ cost(4) }
				}
			}
		}
		builder.node("o") {
			node("p") {
				edge("q")
			}
			node("q") {
				edge("p")
				node("r") {
					node("s") {
						node("t") {
							edge("o"){ cost(3) }
						}
					}
				}
			}
		}
		graph = new Graph(name:'Test_Graph',nodes:builder.nodes)
		algo = new GraphAlgorithms()
	}
	
	void testShortestPaths() {
		/*// For DEBUG 
		new File("/home/noah/tmp/foo.dot").withWriter { it << graph }//*/
		
		def result = algo.shortestPaths(graph,n('a'))
		assertTrue("Algorithm failed.",result.success)
			
		assertTrue(result.distance.toString(),[
		     (n('a')): 0,
		     (n('b')): 1,
		     (n('c')): 0,
		     (n('d')): 1,
		     (n('e')): 1,
		     (n('f')): 2,
		     (n('g')): 1,
		     (n('h')): 2,
		     (n('n')): 2
          ] == result.distance)
		assertTrue(result.predecessor.toString(),[
		     (n('b')): n('a'),
		     (n('c')): n('b'),
		     (n('d')): n('c'),
		     (n('e')): n('c'),
		     (n('f')): n('e'),
		     (n('g')): n('a'),
		     (n('h')): n('g'),
		     (n('n')): n('g')
          ] == result.predecessor)
	}
	
	void testFastSortestPath() {
		// must use part of graph without negative weights
		def result = algo.fastShortestPaths(graph,n('o'))
		
		assertTrue(result.distance.toString(),[
		     (n('o')): 0,
		     (n('p')): 1,
		     (n('q')): 1,
		     (n('r')): 2,
		     (n('s')): 3,
		     (n('t')): 4
        ] == result.distance)
		assertTrue(result.predecessor.toString(),[
		     (n('p')): n('o'),
		     (n('q')): n('o'),
		     (n('r')): n('q'),
		     (n('s')): n('r'),
		     (n('t')): n('s')
        ] == result.predecessor)
	}
}
